<!--░░░░░░░░▌▒█░░░░░░░░░░░▄▀▒▌-->
<!--░░░░░░░░▌▒▒█░░░░░░░░▄▀▒▒▒▐-->
<!--░░░░░░░▐▄▀▒▒▀▀▀▀▄▄▄▀▒▒▒▒▒▐-->
<!--░░░░░▄▄▀▒░▒▒▒▒▒▒▒▒▒█▒▒▄█▒▐-->
<!--░░░▄▀▒▒▒░░░▒▒▒░░░▒▒▒▀██▀▒▌-->
<!--░░▐▒▒▒▄▄▒▒▒▒░░░▒▒▒▒▒▒▒▀▄▒▒-->
<!--░░▌░░▌█▀▒▒▒▒▒▄▀█▄▒▒▒▒▒▒▒█▒▐-->
<!--░▐░░░▒▒▒▒▒▒▒▒▌██▀▒▒░░░▒▒▒▀▄-->
<!--░▌░▒▄██▄▒▒▒▒▒▒▒▒▒░░░░░░▒▒▒▒-->
<!--▀▒▀▐▄█▄█▌▄░▀▒▒░░░░░░░░░░▒▒▒-->
<!--The single doge JUST LOOKING AT YOU without any words.-->
<!--单身犬默默地看着你，一句话也不说。                       -->
<!--                                            07/15/2016-->
<!doctype html>
<html style="height:100%;">
<head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width,initial-scale=1.0, minimum-scale=1.0, maximum-scale=1.0,minimal-ui"/>
    <link href="http://www.qlcoder.com//uploads/145620041535888.png" type="image/x-icon" rel=icon>
    <title>千里码-技能点</title>
    <link href="http://www.qlcoder.com//css/bootstrap.min.css" rel="stylesheet">
    <link href="http://www.qlcoder.com//css/bootstrap-theme.css" rel="stylesheet">
    <link href="http://www.qlcoder.com//css/jquery.mCustomScrollbar.css" rel="stylesheet">
    <link href="http://www.qlcoder.com//css/base.css" rel="stylesheet">
    <link rel="stylesheet" href="http://www.qlcoder.com//font/iconfont.css">


    <link href="http://www.qlcoder.com//css/base.css" rel="stylesheet">
    <link href="http://www.qlcoder.com//css/login.css" rel="stylesheet">
    <link href="/css/challenges.css" rel="stylesheet">

    <link rel="stylesheet" href="http://www.qlcoder.com/css/codemirror.css">
    <link rel="stylesheet" href="http://www.qlcoder.com/js/display/fullscreen.css">
    <style>
        /*2016-06-18 @diego*/
        .codeMirrorTool{
            padding: 5px;
            background: #f6f6f6;
            border: 1px solid #bbb;
            border-bottom: none;
            overflow: hidden;
        }
        .codeMirrorTool .fullScreen,.codeLanguage{
            float: right;
        }
        .fullScreen{
            margin-left: 10px;
        }
        .rank .row{
            /*	border-bottom: 1px solid #ddd;*/
        }
        .rank .row:nth-child(odd) {
            background:#f5f5f5;
        }
        .rank .row div{
            padding-top:5px;
            padding-bottom:5px;
        }
        a.tag{
            font-size: 12px;
            border: 1px solid #ddd;
            padding: 1px 6px;
            border-radius: 5px;
            margin-left: 10px;
            color: green;
            background-color: rgba(1,126,102,.08);
        }
    </style>
</head>
<body class="html-margin">
<div class="q_warp" style="min-height:100%;margin-bottom:-60px;">
    <nav class="nav">
        <!--<div style="width:8.33%;height: 50px;float: left;"></div>-->
        <div class="container-fluid"><!--fluid-->
            <div class="pull-left">
                <a class="" href="/home" style="display: inline-block;"><img src="/img/ql_logo1.png"> </a>
            </div>
            <div class="pull-left nav-list">
                <ul class="" style="padding:0;">
                    <li class="">
                        <a href="/home"><span color="gray" style="font-size:15px;">技能树</span></a>
                    </li>
                    <li class="active">
                        <a href="/discuss/all"><span color="gray" style="font-size:15px;">讨论区</span></a>
                    </li>
                    <li class="">
                        <a href="/article/all"><span color="gray" style="font-size:15px;">文章</span></a>
                    </li>
                    <li class="">
                        <a href="/rank"><span color="gray" style="font-size:15px;">排行榜</span></a>
                    </li>
                    <li class="">
                        <a href="/help"><span color="gray" style="font-size:15px;">帮助中心</span></a>
                    </li>
                    <!-- <li class=""><a href="/help#opinion"><span color="gray" style="font-size:15px;">意见反馈<span></span></span></a></li> -->
                </ul>
            </div>
            <div class="pull-right ">
                <ul class="avator pull-right">
                    <li class="dropdown">
                        <a class="dropdown-toggle pull-left" data-toggle="dropdown"
                           role="button" aria-haspopup="true" aria-expanded="false">
                            <img style="max-width:100px; margin-top: -20px;margin-bottom: -15px;margin-right: 10px;"
                                 src="/system/App/User/avatars/000/000/347/thumb/2000.gif" class="img-circle" alt="cinque terre"
                                 width="30" height="30">

                            <!--<span class="badge s_tip">4</span>-->
                            &nbsp;&nbsp;<span color="gray" style="font-size:15px;">端着木鱼敲代码&nbsp;</span>
                            <span class="caret"></span>
                        </a>
                        <!--<span class="badge s_tip">4</span>-->
                        <ul class="dropdown-menu ">
                            <li><a href="/profile/792c"
                                   target="_blank"><i class="iconfont">&#xe612;</i>我的主页</a></li>
                            <li><a href="/u/update" target="_blank"><i class="iconfont">&#xe603;</i>设置</a>
                            </li>
                            <li><a href="/imglib" target="_blank"><i class="iconfont">&#xe61b;</i>图片库</a>
                            </li>
                            <li><a href="/inbox" target="_blank"><i class="iconfont">&#xe607;</i>私信
                            </a></li>
                            <!--<li role="separator" class="divider"></li>-->
                            <li><a href="/logout" target="_blank"><i class="iconfont">
                                &#xe613;</i>退出</a></li>
                        </ul>
                    </li>
                </ul>
            </div>
        </div>

    </nav>
    <div class="contain">
        <div class="challenge-header">
            <div class="container">
                <div class="clearfix mt15 mb5">
                    <h2 class="hr_tour-challenge-name pull-left mlT">
                        #147: Rectangles in cross-hatched grids
                    </h2>
                </div>
                <div class="clearfix mb20 mt5">
                    <img src="https://hr-avatars.s3.amazonaws.com/ae5358e3-24f6-4d1b-8804-483a0baf5ea4/150x150.png" height="25" width="25" class="avatar pull-left mri10">
                    <span class="small bold">by <a class="backbone color-blue" href="">shashank21j</a></span>
                </div>
            </div>
            <div class="container">
                <div class="module mb20">
                    <ul class="menu-nav horizontal">
                        <li class="active">
                            <a href="">赛题详情</a>
                        </li>
                        <li>
                            <a href="">排行榜</a>
                        </li>
                        <li>
                            <a href="">奖项设置</a>
                        </li>
                        <li>
                            <a href="">讨论区</a>
                        </li>
                        <li>
                            <a href="">判题进程</a>
                        </li>
                    </ul>
                </div>
            </div>
        </div>
        <section class="challenge-wrap">
            <div class="challenge-body">
                <div class="container">
                     <!-- 这里放挑战描述 s-->
					 <div style="padding:0 20px;">
                    <p class="lead"><p>春节福利-遗传算法</p>
                    <p>遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。</p>
                    <p>对于很多最优化问题，由于解空间无限大，所以靠枚举所有局面是基本不可能的。
                        因此我们需要遗传算法或者模拟退火算法等能在有限时间内找到近似最优解的方案。</p>
                    <p>以下这个问题，就非常适合用类似的方法去得到近似最优解。</p>
                    <p>通过随机一个局面作为初始基因，然后通过遗传进行优胜劣汰。
                        变异的存在也可以很好的避免陷入局部最优解。</p>
                    <hr />
                    <p>有n个矩形小纸片(n<=100),它们的长宽各不相同,需要你放在一个长宽均不超过100的矩形桌面上。</p>
                    <p>放置的规则如下:</p>
                    <ol>
                        <li>每个小纸片最多只能被放置1次,也可以选择不放。</li>
                        <li>你可以将小纸片放置在桌面上的任意位置,但不能超出桌面的边界。</li>
                        <li>小纸片之间不能相互叠压,无任何面积重叠。</li>
                        <li>每个小纸片你都可以缩小或者放大（长宽比不能变）,长宽最大可以放大到2倍，最小可以缩小到原来的十分之一。（举例:1个15*13的小纸片,可以放大到30*26,也可以缩小至1.5*1.3）。</li>
                        <li>
                            <p>每张小纸片只有两种放置方法，直接放置或者旋转90°放置。直接放置的小纸片我们称之为A类小纸片,旋转90°之后放置的小纸片我们称之为B类小纸片。</p>
                        </li>
                        <li>当两个不同种类的小纸片相邻,如果他们相邻的线段的长度是x,你的得分将增加x。</li>
                        <li>当两个相同种类的小纸片相邻,如果他们相邻的线段的长度是x,你的得分将减少x。</li>
                    </ol>
                    <p>请你给出一个放置方案，使你的得分最高。</p>
                    <p>为了便于简化问题以及更方便的评测:</p>
                    <ul>
                        <li>
                            <p>你放置矩形的x,y坐标最多保留1位小数。这意味着乘以10之后,它们的值都是一个整数。举例:</p>
                            <ul>
                                <li>你可以把1个纸片的左上角放在(1.3,1.3)位置。</li>
                                <li>你不可以把1个纸片的左上角放在(1.35,1.35)位置。</li>
                            </ul>
                        </li>
                        <li>小纸片被缩放后,它们的长和宽最多保留1位小数。这意味着乘以10之后,它们的值都是一个整数。举例:
                            <ul>
                                <li>你可以把1个15*13的纸片缩放为3.0*2.6。</li>
                                <li>你不可以把1个15*13的纸片缩放为15.75*13.65，虽然长宽比是一样的。</li>
                                <li>你不可以把3*7的纸片缩小7倍变成0.4(0.4286四舍五入)*1,因为四舍五入是不被允许的，这样会使长宽比不一致。</li>
                            </ul></li>
                    </ul>
                    <hr />
                    <p>这里有个<a target="_blank" href="/train/gatool">传送门</a>，里面包括如下内容:</p>
                    <ul>
                        <li>
                            <p>工具箱内陈列着所有的小纸片,你可以把这些小纸片放置在右侧的桌面上。</p>
                            <ul>
                                <li>按+号是放大小纸片。</li>
                                <li>按-号是缩小小纸片。</li>
                                <li>按空格是选择A类或者B类小纸片。</li>
                            </ul>
                        </li>
                        <li>
                            <p>红色的input按钮可以选择某个具体input文件。</p>
                            <ul>
                                <li>input文件的第一行是2个整数,分别代表桌面的长(x轴)和高(y轴)。</li>
                                <li>input文件的第二行是一个整数n,代表小纸片的个数。</li>
                                <li>input文件接下来有n行，每行2个整数，代表每个小纸片的长(x轴)和高（y轴）。</li>
                            </ul>
                        </li>
                        <li>
                            <p>对于每个input文件，最终你需要提供1个output文件。</p>
                            <ul>
                                <li>该文件有n行，每行代表一个小纸片。</li>
                                <li>每行有4个浮点数，分别代表每个小纸片左下角坐标(x1,y1)和右上角坐标(x2,y2)。</li>
                                <li>如果你不准备把某个小纸片放置在桌面上,那么该行为"-1 -1 -1 -1"。    </li>
                            </ul>
                        </li>
                        <li>该题的得分为这10个input文件你所得到的总分。</li>
                    </ul>
                    <p>PS:非常感谢@ikarienator提供的gatool。</p></p>
				</div> <!-- 这里放挑战描述 e-->
                </div>
                <div style="overflow:hidden;">                <!-- Comments Form -->
                    <h4>答案:</h4>

                    <div class="form-group">
                        <input type="hidden" name="_token" value="qu1yHPvWdc28khuP1MqE0GPrFnuYWCaq1OWfteFa">
                        <input type="hidden" name="phref" value="/task/138/solve">

                        <div class="codeMirrorTool">
                            <button class="fullScreen">全屏</button>
                            <select class="codeLanguage">
                                <option data="text/x-python" value="python">python2.7</option>
                                <option data="text/x-csrc" value="qll">qll</option>
                                <!--  <option data="text/javascript" value="javascript">javascript</option>-->
                                <!-- <option data="text/x-java" value="java">java</option>-->
                            </select>
                        </div>

                        <textarea id="editor" name="editor">
                        def encode(num):
                            #todo
                            return str


                        def decode(str):
                            #todo
                            return num
                        </textarea>
                    </div>
                    <button type="submit" class="btn btn-primary solve pull-right">提交</button>

                </div>
            </div>
        </section>
    </div>
    <div style="height:60px;"></div>
</div>


<div class="task-shadow none"></div>
<img class="loadding_img none" src="/img/loadding.gif" alt="正在加载中" style="display: block;position: fixed;top: 50%;left: 50%;margin-top: -10px;margin-left: -50px;">
<div class="authority none" style="width:550px;position:fixed;top:50%;left:50%;margin-top:-265px;margin-left:-275px;z-index: 2222222">
    <div class="authority-warp" style="position:relative">
        <a href="javascript:;" class="authority-close" style="position:absolute;top:6px;right:10px;">X</a>
        <div class="panel panel-login">
            <h2 style="margin-left: 30px;">千里码</h2>

            <p style="font-size: 18px;margin-left: 30px;">Code is cheap,show me the answer.</p>
            <!--<h2 style="margin-left: 30px;">千里码</h2>

        <p style="font-size: 18px;margin-left: 30px;">与开发者分享你的技术和实战经验</p>-->
            <div class="panel-heading">
                <div class="row">
                    <div class="col-xs-6">
                        <a href="#" class="active" id="login-form-link">登录</a>
                    </div>
                    <div class="col-xs-6">
                        <a href="#" id="register-form-link" class="">注册</a>
                    </div>
                </div>
                <hr>
            </div>
            <div class="panel-body">
                <div class="row">
                    <div class="col-lg-12">
                        <form id="login-form" action="/auth/login" method="post" role="form" style="display: block;">
                            <input type="hidden" name="_token" value="qu1yHPvWdc28khuP1MqE0GPrFnuYWCaq1OWfteFa">
                            <div class="form-group">
                                <input type="text" name="email" id="email" tabindex="1" class="form-control" placeholder="邮箱" value="">
                            </div>
                            <div class="form-group">
                                <input type="password" name="password" id="password" tabindex="2" class="form-control" placeholder="密码">
                            </div>
                            <div class="form-group text-center">
                                <input type="checkbox" tabindex="3" class="" name="remember" id="remember">
                                <label for="remember"> 记住我</label>
                            </div>
                            <div class="form-group">
                                <div class="row">
                                    <div class="col-sm-6 col-sm-offset-3">
                                        <input type="submit" name="login-submit" id="login-submit" tabindex="4" class="form-control btn btn-login" value="登录">
                                    </div>
                                </div>
                            </div>
                            <div class="form-group">
                                <div class="row">
                                    <div class="col-lg-12">
                                        <div class="text-center">
                                            <a href="/password/email" tabindex="5" class="forgot-password">忘记密码?</a>
                                        </div>
                                    </div>
                                </div>
                            </div>
                        </form>
                        <form id="register-form" action="/auth/register" method="post" role="form" style="display: none;">

                            <input type="hidden" name="_token" value="qu1yHPvWdc28khuP1MqE0GPrFnuYWCaq1OWfteFa">
                            <div class="form-group">
                                <input type="hidden" name="utm" id="utm" value="unknown">
                            </div>
                            <div class="form-group">
                                <input type="text" name="name" id="name" tabindex="1" class="form-control" placeholder="用户名" value="">
                            </div>
                            <div class="form-group">
                                <input type="email" name="email" id="email" tabindex="1" class="form-control" placeholder="邮箱" value="">
                            </div>
                            <div class="form-group">
                                <input type="password" name="password" id="password" tabindex="2" class="form-control" placeholder="密码">
                            </div>
                            <div class="form-group">
                                <input type="password" name="password_confirmation" id="password_confirmation" tabindex="2" class="form-control" placeholder="再次输入密码">
                            </div>
                            <div class="form-group">
                                <div class="row">
                                    <div class="col-sm-6 col-sm-offset-3">
                                        <input type="submit" tabindex="4" class="form-control btn btn-register" value="提交">
                                    </div>
                                </div>
                            </div>
                        </form>
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>
<div class="result-alert none">
    <div class="result_warp">
        <div class="warning">
            <i class="iconfont">&#xe616;</i><!-- true:&#xe617;   flase:&#xe616;  -->
        </div>
        <p>我是一条安安静静摸鱼的咸鱼~</p>
        <div class="query"><a class="btn btn-primary result-close">确定</a></div>
    </div>

</div>
<!-- Footer -->
<footer>
    <p>©2016 千里码 浙ICP备15038807号-1 联系我们:oreo@qlcoder.com <a target="_blank" href="http://shang.qq.com/wpa/qunwpa?idkey=08dcd44232943b517c2ed04dceb097155575f604791c57bbd2f9759e90e22d58">qq群480394714</a>
    </p>
</footer>
<script src="http://www.qlcoder.com//js/jquery.min.js"></script>
<script src="http://www.qlcoder.com//js/bootstrap.min.js"></script>
<script src="http://www.qlcoder.com//js/base.js"></script>
<script src="http://www.qlcoder.com/js/login.js"></script>
<script src="http://www.qlcoder.com/js/codemirror.js"></script>
<script src="http://www.qlcoder.com/js/mode/python/python.js"></script>
<script src="http://www.qlcoder.com/js/mode/clike/clike.js"></script>
<script src="http://www.qlcoder.com/js/mode/javascript/javascript.js"></script>
<script src="http://www.qlcoder.com/js/display/fullscreen.js"></script>
<script type="text/javascript">
    var testEditor;
    //is pass?
    var _flag=false;
    $(function() {
        codeMirrorEditor();
        var javascript="console.log('hello world')";
        var python=$("#editor").html();
        var codeLanuage={javascript:javascript,python:python};
        $("select").change(function(){
            var type=$(this).find("option:selected").val();
            var child=$(this).find("option:selected").attr('data');

            $("#editor").html(codeLanuage[type]);
            $(".CodeMirror").remove();
            codeMirrorEditor(child);
        })

        $("button.solve").click(function(){
            var val=$("textarea.form-control").val() || localStorage.getItem("codeMirror");
            var token=$("input[name='_token']").val();
            var _href=$("input[name='phref']").val();
            var lan= "" || $(".codeLanguage").val() ;
            $(".task-shadow").toggleClass("none");
            $(".loadding_img").removeClass("none");
            $.ajax({
                url:_href,
                timeout:30000,
                type:"post",
                data:{answer:val,_token:token,lan:lan},
                dataType:"json",
                success:function(data){
                    if(data.success==true)
                    {
                        $(".result_warp").removeClass("none");
                        $(".result-alert").toggleClass("none").find(".warning").find("i").html("&#xe617;").css("color","#2aa515");
                        $(".result-alert p").html(data.result);
                        _flag=true;
                    }
                    else{
                        /* $(".result_warp").removeClass("none");
                         $(".result-alert").toggleClass("none").find(".warning").find("i").html("&#xe616;");
                         $(".result-alert p").html(data.result);*/
                        if($("#taskType").val()==1){//区分代码题还是普通题，代码题错误的话不弹框
                            $("#codeError").show().html(data.result);
                            $(".task-shadow,.result-alert,.loadding_img").addClass('none');
                            window.location.hash="codeError";
                        }else{
                            $(".result_warp").removeClass("none");
                            $(".result-alert").toggleClass("none").find(".warning").find("i").html("&#xe616;");
                            $(".result-alert p").html(data.result);
                        }
                    }
                },
                complete:function(XMLHttpRequest,status){
                    if(status=='timeout'){
                        $(".result_warp").removeClass("none");
                        $(".result-alert").toggleClass("none").find(".warning").find("i").html("&#xe616;");
                        $(".result-alert p").html("请求超时，请重新尝试！");
                    }
                }
            })

        });
        $(".commentLogin").click(function(){
            $(".authority,.task-shadow").removeClass("none");
        })
        $(".result-close").click(function(){
            if(_flag){
                window.location.reload();
            }
            else{
                $(".task-shadow").addClass("none");
                $(".result-alert").addClass("none");
                $(".loadding_img").addClass("none");
            }
        })
        $(".authority-close").click(function(){
            $(".authority,.task-shadow").addClass("none");
        });
    });
    function codeMirrorEditor(mode){
        var myTextarea = document.getElementById('editor');
        var CodeMirrorEditor = CodeMirror.fromTextArea(myTextarea, {
            mode: mode || "text/x-python",
            lineNumbers: true,
//            value: localStorage.getItem("codeMirror") || "",
            extraKeys: {
                "F11": function(cm) {
                    cm.setOption("fullScreen", !cm.getOption("fullScreen"));
                },
                "Esc": function(cm) {
                    if (cm.getOption("fullScreen")) cm.setOption("fullScreen", false);
                    $(".fullScreen").removeAttr("style").html("全屏");
                }
            }
        });
        $(".fullScreen").click(function(){
            CodeMirrorEditor.setOption("fullScreen", !CodeMirrorEditor.getOption("fullScreen"));
            if(CodeMirrorEditor.getOption("fullScreen")) {
                $(this).css({"position":"fixed","top":"5px","right":"5px","z-index":"11"}).html("取消全屏");
            }else{
                $(this).removeAttr("style").html("全屏");
            }
        });
        localStorage.setItem("codeMirror",$("#editor").val());
        //load code
        /*if(localStorage.getItem('codeMirror')){
         CodeMirrorEditor.setOption("value",localStorage.getItem("codeMirror") || "");
         }*/
        //save code
        CodeMirrorEditor.on("change",function(){
            localStorage.setItem("codeMirror", CodeMirrorEditor.getValue());
            console.log(localStorage.getItem("codeMirror"));
        })
    }
</script>
</body>
</html>


